
// // Definition for a Node.
// class Node {
// public:
//     int val;
//     Node* left;
//     Node* right;
//     Node* next;

//     Node() : val(0), left(NULL), right(NULL), next(NULL) {}

//     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

//     Node(int _val, Node* _left, Node* _right, Node* _next)
//         : val(_val), left(_left), right(_right), next(_next) {}
// };


class Solution {
public:
    Node* connect(Node* root) {
        //人为的确定每一层有多少个，完成进入下层前的所有处理
        if(!root) return NULL;
        queue<Node*> q;q.push(root);
        while(!q.empty()){
           int layerSize = q.size();
           Node *lastptr = NULL;
            for(int i=1;i<=layerSize;i++){
                Node *temp = q.front();q.pop();
                
                if (temp->left){
                    q.push(temp->left);
                }
                if (temp->right){
                    q.push(temp->right);
                }
                if (i!=1){
                    lastptr->next = temp;//本层上一个的next指向当前节点   
                    lastptr = temp;//上一个指向现在的结点，把现在的当做下一次的上一个结点
                }else lastptr = temp; //本层第一个，把自己作为下一个的“前一个节点”

            }

        }
        return root;
    }
};